#include<stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream>

// 单链表带头结点

typedef int ElemType;  // 定义元素类型

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

// 初始化,建立头结点
bool InitList(LinkList &L){
    L=(LNode*)malloc(sizeof(LNode));  // 创建头结点
    if (L==NULL) return false;
    L->next=NULL;                       // 空链表
    return true;
}

// 插入
bool ListInsert(LinkList &L, int i, ElemType e){
    if (i<1) return false;
    LNode *p;
    int j=0;
    p = L;
    while (p!=NULL && j<i-1) {     // 循环找到第i-1个结点
        p=p->next;
        j++;
    }
    if (p==NULL) return false;     // i值不合法
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;                  // 将结点s连到p之后
    return true;                  // 插入成功  
}

// 后插
bool InsertNextNode(LNode *p, ElemType e){
    // 如果这个结点是空的，就是插入失败
    if (p==NULL) return false;
    // 如果这个结点不是空的，继续
    // 创建一个新的结点
    LNode *s = (LNode *)malloc(sizeof(LNode));
    // 分配内存失败
    if (s==NULL) return false;
    // 赋值
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

// 前插
bool InsertPriorNode(LNode *p, ElemType e){
    if (p==NULL) return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s==NULL) return false;
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}

// 根据位序删除元素
bool ListDelete(LinkList &L, int i, ElemType &e){
    if (i<1) return false;
    LNode *p = L;
    int j=0;
    while (p!=NULL && j<i-1)
    {
        p = p->next;
        j++;
    }
    if (p==NULL) return false;
    if (p->next == NULL) return false;
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

// 删除指定结点p
bool DeleteNode(LNode *p){
    if (p==NULL) return false;
    LNode *q = p->next;
    p->next = q->next;
    p->data = q->data;
    free(q);
    return true;
}

// 根据位序取出元素
LNode *GetElem(LinkList L, int i){
    int j=1;
    LNode *p = L->next;
    if (i==0) return L;
    if (i<0) return NULL;
    while (p!=NULL && j<i)
    {
        p=p->next;
        j++;
    }
    return p;
}

// 输出
void PrintList(LinkList L){
    L = L->next;
    while (L != NULL) {
        printf("%d;", L->data);
        L = L->next;
    }
}

int main(){
    LinkList L;
    ElemType e;
    InitList(L);
    ListInsert(L, 1, 1);
    ListInsert(L, 1, 2);
    ListInsert(L, 1, 3);
    PrintList(L);
    printf("\n");
    InsertNextNode(GetElem(L, 2), 66);
    PrintList(L);
    printf("\n");
    InsertPriorNode(GetElem(L, 2), 77);
    PrintList(L);
    printf("\n");
    // ListDelete(L, 2, e);
    DeleteNode(GetElem(L, 2));
    PrintList(L);
    printf("\n");
    // printf("delete : %d", e);
    system("pause");
    return 0;
}
